package com;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class TSGreedy {
	
	/*This method uses the greedy algorithm (aka nearest neighbour) to solve TS.*/
	
	static double compute(SimpleWeightedGraph<Node, DefaultWeightedEdge> graph) {
		 
		//Initialise minDist to zero.
		double minDist = 0.0;
		
		double smallestEdge;
		
		//HashSet offers constant-time performance on the 'contains' operation, the only one we need.
		HashSet<Node> visitedNodes = new HashSet<Node>();
		
		//An array list to hold the nodes in the order visited to then convert them into waypoints. 
		ArrayList<Node> nodeList = new ArrayList<Node>();
		
		//Get all nodes in the graph.
		Set<Node> vertices = graph.vertexSet();
		
		//Pick any vertex to start.
		Iterator<Node> iterN = vertices.iterator();
		Node activeNode = iterN.next();
		
		//A reference to the 1st node visited.
		Node firstNode = activeNode;
		
		//Iterate through the vertices.
		while (!(visitedNodes.size() >= vertices.size())) {
								//reset to infinity at start of new vertex.
								smallestEdge = Double.POSITIVE_INFINITY;
								
								//reset the 'next vertex' pointer.
								Node nextNode = null;
								
								//iterate through all the edges connected to the vertex.
								Set<DefaultWeightedEdge> edgesFromNode = graph.edgesOf(activeNode);
								Iterator<DefaultWeightedEdge> iterE = edgesFromNode.iterator();
								while (iterE.hasNext()) {
														//get a random edge connected to the vertex.
														DefaultWeightedEdge edge = iterE.next();
														//find the target vertex of the edge.
														Node node = graph.getEdgeSource(edge);
														Node targetNode;
														if (node.equals(activeNode)) {targetNode = graph.getEdgeTarget(edge);}
														else {targetNode = node;}
														//get weight of the edge.
														double weight = graph.getEdgeWeight(edge);
														//if the new edge is smaller than the ones seen so far, update value and pointer to its target vertex. 
														if (weight <= smallestEdge && !visitedNodes.contains(targetNode)) 
															{smallestEdge = weight;
															nextNode = targetNode;}
														else {}
														}
								//mark the current vertex as 'visited'.
								visitedNodes.add(activeNode);
								//add it to the array list of nodes.
								nodeList.add(activeNode);
								//test if we are at the last vertex, where smallestEdge doesnt get updated 
								//so it stays as infinity. in that case, update minTime with edge from last 
								//vertex back to the 1st one. otherwise, update with weight of this edge.
								if (smallestEdge != Double.POSITIVE_INFINITY) {
													minDist += smallestEdge;
								} else {minDist += graph.getEdgeWeight(graph.getEdge(firstNode, activeNode));}
								//update the pointer to next vertex to be visited.
								activeNode = nextNode;
								
		}	
		
		//convert the nodes into waypoints (in the correct order)
		for (Node node : nodeList) {
			String waypoint = node.lat + ", " + node.lon;
			AlibiTesterApplet.waypoints.add(waypoint);
		}
		//and finally add the first node again at the end to complete loop.
		AlibiTesterApplet.waypoints.add(AlibiTesterApplet.waypoints.get(0));
		
		return minDist;					
		
	}
}
